package com.beaven.java.sort;

/**
 * @author Beaven
 * @date 2018/7/8 17:56
 * <p>
 * 堆排序
 * <p>
 * {http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/}
 */
public class HeapSort {

    /**
     * 堆排序分两步，
     * 第一步构造出堆，不管最底层的堆元素，
     * 第二步，进行元素的下沉排序
     */
    public static void sort(int[] nums) {
        int len = nums.length - 1;
        // 第一步，构造堆
        for (int i = len / 2; i >= 0; i--) {
            sink(nums, i, len);
        }
        // 第二步，
        while (len > 0) {
            // 把最后面的一个元素放到最上面
            exch(nums, 0, len--);
            // 进行下沉排序，也就是父节点向下比对，交换
            sink(nums, 0, len);
        }
    }


    /**
     * 下沉排序，找到两个子节点中的大值，父节点与之比较，完成小值得下降
     */
    private static void sink(int[] nums, int k, int n) {
        while (2 * k + 1 <= n) {
            // 左子节点
            int j = 2 * k + 1;
            if (j < n && nums[j] < nums[j + 1]) {
                j++;
            }
            if (nums[k] > nums[j]) {
                break;
            }
            exch(nums, k, j);
            k = j;
        }
    }

    /**
     * 上浮排序，子节点与父节点比较，完成大值得上升
     */
    private static void swim(int[] nums, int k, int n) {
        while (k > 1 && nums[(k - 1) / 2] < nums[k]) {
            exch(nums, (k - 1) / 2, k);
            k = (k - 1) / 2;
        }
    }

    private static void exch(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
